package org.example.linkedlist;

public class ReorderList {

    /**
     * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
     *
     * L0 → L1 → … → Ln - 1 → Ln
     * 请将其重新排列后变为：
     *
     * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
     * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     * @param head
     */
    public void reorderList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null){
            return;
        }
        //找到链表的中间节点，将之后的节点逆序为一个新链表，再将两个链表交替合并
        //1.利用快慢指针找到链表中间节点
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //2.将后半部分链表逆序
        ListNode temp = reverse(slow.next);
        slow.next = null;
        //3.合并
        merge(head,temp);
    }
    // 交替合并两个链表
    public void merge(ListNode cur1, ListNode cur2) {
        ListNode next1;
        ListNode next2;
        while (cur1 != null && cur2 != null) {
            next1 = cur1.next;
            next2 = cur2.next;

            cur1.next = cur2;
            cur2.next = next1;

            cur1 = next1;
            cur2 = next2;
        }
    }
    //头插法
    public ListNode reverse(ListNode head){
        ListNode newHead = new ListNode();
        ListNode cur = head;
        while(cur!=null){
            ListNode tmp = newHead.next;
            newHead.next = cur;
            cur = cur.next;
            newHead.next.next = tmp;
        }
        return newHead.next;
    }
    public class ListNode {
     int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
}
